//
// Created by zhulingfeng on 2020/2/28.
//

#include "insertion_sort.hpp"
#include "utils/utils.hpp"
void InsertionSort(std::vector<int>& vector) {
  for (int i = 1; i < vector.size(); ++i) {
    for (int j = i; j >= 1; j--) {
      if (vector[j] < vector[j - 1]) {
        swap(vector, j, j - 1);
      } else {
        break;
      }
    }
  }
}
void InsertionSort(std::vector<int>& vector, int lo, int hi) {
  for (int i = lo + 1; i <= hi; ++i) {
    for (int j = i; j >= lo + 1; j--) {
      if (vector[j] < vector[j - 1]) {
        swap(vector, j, j - 1);
      } else {
        break;
      }
    }
  }
}
ListNode* InsertionUnstableSort(ListNode* head) {
  ListNode dummy;
  while (head) {
    auto beforeResNode = &dummy;
    auto resNode = dummy.next;
    while (resNode) {
      // Stop when <= makes sorted result unstable.
      if (head->val <= resNode->val) {
        // beforeResNode->next=head;
        // head=head->next;
        // beforeResNode->next->next=resNode;
        break;
      } else {
        beforeResNode = resNode;
        resNode = resNode->next;
      }
    }
    beforeResNode->next = head;
    head = head->next;
    // beforeResNode->next->next = nullptr;
    beforeResNode->next->next = resNode;
  }
  return dummy.next;
}
ListNode* InsertionStableSort(ListNode* head) {
  ListNode dummy;
  while (head) {
    auto beforeResNode = &dummy;
    auto resNode = dummy.next;
    while (resNode) {
      // Stop when < makes sorted result stable.
      if (head->val < resNode->val) {
        // beforeResNode->next=head;
        // head=head->next;
        // beforeResNode->next->next=resNode;
        break;
      } else {
        beforeResNode = resNode;
        resNode = resNode->next;
      }
    }
    beforeResNode->next = head;
    head = head->next;
    // beforeResNode->next->next = nullptr;
    beforeResNode->next->next = resNode;
  }
  return dummy.next;
}
